#ifndef __BINARY_TREE_H_
#define __BINARY_TREE_H_

#include "queue.h"

/*二叉树节点*/
struct BinaryTreeNode
{
    /*构造函数*/
    BinaryTreeNode(ELEMENT_TYPE date, BinaryTreeNode *left, BinaryTreeNode *right, BinaryTreeNode *parent)
    {
        m_data = date;
        m_left = left;
        m_right = right;
        /*父结点 */
        m_parent = parent;
    }
    /*数据*/
    ELEMENT_TYPE m_data;

    /*左子树*/
    BinaryTreeNode *m_left;
    /*右子树*/
    BinaryTreeNode *m_right;
    /*父节点 */
    BinaryTreeNode *m_parent;
};

class BinaryTree
{
public:
    /*构造函数*/
    BinaryTree(int (*compareFunc)(ELEMENT_TYPE arg1, ELEMENT_TYPE arg2), void (*printFunc)(ELEMENT_TYPE arg));

    /*析构函数*/
    ~BinaryTree();

public:
    /*插入数据*/
    void insertData(ELEMENT_TYPE data);

    /*是否包含*/
    bool isContainData(ELEMENT_TYPE data);

    /*层序遍历*/
    void levelTravel();
    /* 删除数据 */
    void deleteData(ELEMENT_TYPE data);

    /*前序遍历*/
    void preOrderTravel();
    /*中序遍历 */
    void inorderTravel();
    /*后序遍历 */
    void postorderTravel();

private:
    /*度为2 */
    bool hasTwochildren(BinaryTreeNode *node);
    /*度为1 */
    bool hasOnechildren(BinaryTreeNode *node);
    /*度为0(叶子结点)*/
    bool isLeaf(BinaryTreeNode *node);

    // 根据指定的值得到树的结点
    BinaryTreeNode *getAppointNode(ELEMENT_TYPE data);
    /*前驱结点*/
    BinaryTreeNode *getPreDecessor(BinaryTreeNode *node);
    /*后继结点 */
    BinaryTreeNode *getSuccessor(BinaryTreeNode *node);
    /*判断当前节点是父节点的左边 */
    bool IsLeft(BinaryTreeNode *node);
    /*判断当前节点是父节点的右边 */
    bool IsRight(BinaryTreeNode *node);

    void preOrder(BinaryTreeNode *travelNode);
    void inorder(BinaryTreeNode *travelNode);
    void postorder(BinaryTreeNode *travelNode);
private:
    /* 根节点 */
    BinaryTreeNode *m_root;
    /*元素个数*/
    int m_size;
    /*比较器*/
    int (*m_compareFunc)(ELEMENT_TYPE arg1, ELEMENT_TYPE arg2);
    /*打印器*/
    void (*m_printFunc)(ELEMENT_TYPE arg);
};

#endif //__BINARY_TREE_H_